package top.humbleyuan.backtrack;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:08
 * @Des 正则匹配
 * @pro 待补充回溯
 */
public class LeetCode_10 {

    public static void main(String[] args) {
        // 自己写的dp
        m1();

        // 一般回溯
        m2();

        // p串从后往前dp
        m3();
    }


    /**
     * 10.正则匹配
     *
     * if p[j](包含.) == s[i]
     *      相当于同时添加一个相同字母，即dp[i][j] == dp[i-1][j-1]
     * if p[j] == "*"
     *      if p[j-1] == s[i]   //说明可匹配
     *          1.*表示0个删除p[j-1],即dp[i][j] == dp[i][j-2]
     *          2.*表示一个，即dp[i][j] == dp[i][j-1]
     *          3.因为s[i] = p[j-1] && p[j] == "*",所以dp[i][j] == dp[i-1][j]
     *              加了个s[i],相当于给p串多加了个p[j-1]
     *       else
     *          dp[i][j] = dp[i][j-2] 即*只能表示0个，去掉两个字符
     *
     */
    public static void m1() {
        String s = "";
        String p = "a*";

        /**
         dp:
         dp[i][j]表示Pi串和Sj串是否匹配
         状态转移：
         1. p[i] = s[j]  =>  dp[i][j] = dp[i - 1][j - 1]
         2. p[i] != s[j] :
         2.1 p[i]是字母  =>  dp[i][j] = false
         2.2 p[i] = '*':
         2.2.1 p[i - 1] != s[j]  表示*是0个 => dp[i][j] = dp[i - 2][j]
         2.2.2 p[i - 1] = s[j] || p[i - 1] == '.':
         a. dp[i][j - 2] 表示*是0个
         b. dp[i][j - 1] 表示*是1个
         c. dp[i - 1][j]表示*是多个
         => a or b or c
         2.3 p[i] = '.'  =>  dp[i][j] = dp[i - 1][j - 1]

         **/
        if(p == null || p == "") {
            if(s == null || s == "") {
                System.out.println(true);
                return ;
            }
            System.out.println(false);
            return ;
        }

        if(s == null || s == "") {
            System.out.println(false);
            return ;
        }



        boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
        dp[0][0] = true;

        for (int i = 1; i < p.length(); i++) {   /*为了消除a*这种与空串的匹配，比如s是空，a*或者a*b*都是满足条件的，执行这个                                                    循环就可以得到满足条件的情况，并设为true*/
            // 这种指*表示0个
            if (p.charAt(i) == '*') {
                dp[i + 1][0] = dp[i - 1][0];
            }
        }

        for(int i = 0;i < p.length();i++) {
            for(int j = 0;j < s.length();j++) {
                if(p.charAt(i) == s.charAt(j) || p.charAt(i) == '.') {
                    dp[i + 1][j + 1] = dp[i][j];
                    continue;
                }

                if(p.charAt(i) == '*'  && i > 0) {
                    if(p.charAt(i - 1) == s.charAt(j) || p.charAt(i - 1) == '.'){
                        dp[i + 1][j + 1] = dp[i - 1][j + 1] || dp[i][j + 1] || dp[i + 1][j];
                    } else{
                        dp[i + 1][j + 1] = dp[i - 1][j + 1];
                    }
                }

            }
        }


        System.out.println(dp[p.length()][s.length()]);
    }

    public static void m2() {
        String s = "";
        String p = "a*";

        System.out.println(dfs(s, p));
    }


    public static boolean dfs(String s, String p) {
        if(p.length() == 0) {
//            if(s.length() == 0) {
//                return true;
//            }
//            return false;

            // 代码简化
            return s.isEmpty();
        }

        // 当前字符是否一样
        boolean isMatch = (!s.isEmpty()) && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');

        // 考虑是*的情况
        if(p.length() > 1 && p.charAt(1) == '*') {
            // 这里分两种情况
            // 1. *表示0个,这种情况无论是当前(两个串)的字符是否匹配都有可能,
            // 如果非isMatch,只能看这种情况，如果isMatch,也有可能表示0个
            // 2. *表示一个或者多个前面的数，那么可以将s一个个往后推
            return dfs(s, p.substring(2)) ||
                    (isMatch && dfs(s.substring(1), p));
        } else {
            // 如果非isMatch直接false
            return isMatch && dfs(s.substring(1), p.substring(1));
        }
    }

    // p串从后往前，思路和回溯相似,和我的dp方法方向相反
    public static void m3() {
        String s = "";
        String p = "a*";

        // dp[i][j]表示s[i:]和p[j:]的串是否匹配
        // 而我的dp表示s[:i]和p[:j]的串是否匹配
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[s.length()][p.length()] = true;  // 可以算做都是空的情况

        // dp[s.length][j](j < p.length) 和 dp[i][p.length](i < s.length)没有赋值
        // 或者说默认为false,而代表的意义分别是s空，p不空和s不空，p空
        // p空，s不空则一定是false,即dp[i][p.length] = false必然成立，也就不用额外赋值
        // 而p不空，s空则不一定，需要额外讨论，所以i要从s.length开始

        for (int i = s.length(); i >= 0; i--) {
            // 看s到i能否和整个p串匹配
            for (int j = p.length() - 1; j >= 0; j--) {
                // i == s.length时表示s当前空，一定不匹配
                boolean isMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');

                // 当前两个字母是否匹配，再看p后一个是否为'*'
                if(j < p.length() - 1 && p.charAt(j + 1) == '*') {
                    // 1. *表示1个或多个，那么我们可以先把s当前i忽略后移，即dp[i+ 1][j]
                    dp[i][j] = dp[i][j + 2] || (isMatch && dp[i + 1][j]);
                } else {
                    dp[i][j] = isMatch && dp[i + 1][j + 1];
                }
            }
        }

    }
}
